package com.jiang.daily.Q2654;

/**
 * @author Jiang
 * @version 1.0
 * @date 2025/11/12 11:32
 */
class Solution {
    public int minOperations(int[] nums) {
        int n = nums.length;
        int res = 0;
        for (int num : nums) {
            if (num != 1) {
                res++;
            }
        }
        // nums中存在1，直接返回
        if (res != n) return res;

        int count = Integer.MAX_VALUE; // 出现1时操作的最小次数
        for (int i = 0; i < n; i++) {
            int temp = nums[i]; // 记录最小公约数
            int cnt = 0; // 本次循环出现1时操作的最小次数
            for (int j = i + 1; j < n; j++) {
                temp = gcd(temp, nums[j]);
                // 出现了1时，并且出现1时只进行了1次操作，直接返回n
                if (temp == 1) {
                    if (cnt == 0) return n;
                    count = Math.min(count, cnt);
                    // 如果将 任意两者之一 替换成它们的最大公约数（题目是将 nums[i] 或者 nums[i+1] 两者之一）
                    // temp = nums[i];
                    // cnt = 0;
                    break; // 题目是相邻，直接结束循环即可
                }
                cnt++;
                // 如果将 任意两者之一 替换成它们的最大公约数（题目是将 nums[i] 或者 nums[i+1] 两者之一）
                // if (temp != nums[i] && temp != nums[j]) {
                //     cnt++;
                // }
            }
        }
        return count == Integer.MAX_VALUE ? -1 : count + res;
    }

    private int gcd(int a, int b) {
        if (b == 0)
            return a;
        return gcd(b, a % b);
    }
}
